package com.zhang.graph.directedgraph;





import java.lang.reflect.Array;
import java.util.*;

/**
 * @author zhang
 * @time 2022/03/02 10:39:36
 */
public class Graph {
    private class Node {
        private List<Edge> edges = new ArrayList<>();
        private String label;

        public Node(String label) {
            this.label = label;
        }

        public List<Edge> getEdges() {
            return this.edges;
        }

        public void addEdge(Node to) {
            this.edges.add(new Edge(this, to));
        }

        @Override
        public String toString() {
            return  label;
        }
    }
    private class Edge{
        private Node to;
        private Node from;

        public Edge(Node from, Node to) {
            this.to = to;
            this.from = from;
        }
        @Override
        public String toString() {
            return from + "->" + to;

        }
    }

    private Map<String, Node> nodes = new HashMap<>();

    public void addNode(String label) {
        nodes.putIfAbsent(label, new Node(label));
    }

    public void addEdge(String from, String to) {
        Node fromNode = nodes.get(from);
        Node toNode = nodes.get(to);
        if (fromNode == null || toNode == null) {
            return;
        }
        fromNode.addEdge(toNode);

    }
    public void traverseDepthFirstRec(String root) {
        Node node = nodes.get(root);
        if (node == null) {
            return;
        }
        traverseDepthFirstRec(node, new HashSet<>());
    }

    private void traverseDepthFirstRec(Node node, Set<Node> visited) {
        System.out.println(node);
        visited.add(node);
        for (Edge edge : node.getEdges()) {
            if (!visited.contains(edge.to)) {
                traverseDepthFirstRec(edge.to,visited);
            }
        }
    }
    public void traverseDepthFirst(String root) {
        Node node = nodes.get(root);
        if (node == null) {
            return;
        }
        Set<Node> visited = new HashSet<>();
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            if (visited.contains(current)) {
                continue;
            }
            visited.add(current);
            System.out.println(current);
            for (Edge edge : current.getEdges()) {
                if (!visited.contains(edge.to)) {
                    stack.push(edge.to);
                }
            }
        }
    }
    public void traverseBreadFirst(String root) {
        Node node = nodes.get(root);
        if (node == null) {
            return;
        }
        Set<Node> visited = new HashSet<>();
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node current = queue.remove();
            if (visited.contains(current)) {
                continue;
            }
            System.out.println(current);
            visited.add(current);

            for (Edge edge : current.getEdges()) {
                if (!visited.contains(edge.to)) {
                    queue.add(edge.to);
                }
            }
        }

    }
    public void topologicalSort() {
        Stack<Node> stack = new Stack<>();
        Set<Node> visited = new HashSet<>();

        for (Node node : nodes.values()) {
            topologicalSort(node,visited,stack);
        }
        List<String> sorted = new ArrayList<>();
        while (!stack.isEmpty()) {
            sorted.add(stack.pop().label);
        }
        System.out.println(sorted);

    }

    private void topologicalSort(Node node, Set<Node> visited, Stack<Node> stack) {
        if (visited.contains(node)) {
            return;
        }
        visited.add(node);
        for (Edge edge : node.getEdges()) {
            topologicalSort(edge.to,visited,stack);
        }
        stack.push(node);
    }
    public boolean hasCycle() {
        Set<Node> all = new HashSet<>();
        Set<Node> visiting = new HashSet<>();
        Set<Node> visted = new HashSet<>();

        all.addAll(nodes.values());
        while (!all.isEmpty()) {
            Node current = all.iterator().next();
            if (hasCycle(current, all, visiting, visted)) {
                return true;
            }
        }
        return false;

    }

    private boolean hasCycle(Node node, Set<Node> all, Set<Node> visiting, Set<Node> visited) {
        all.remove(node);
        visiting.add(node);

        for (Edge edge : node.getEdges()) {
            if (visited.contains(edge.to)) {
                continue;

            }
            if (visiting.contains(edge.to)) {
                return true;
            }
            if (hasCycle(edge.to, all, visiting, visited)) {
                return true;
            }
        }
        visiting.remove(node);
        visited.add(node);
        return false;
    }


    public static void main(String[] args) {

        Graph g = new Graph();
        //遍历
//        g.addNode("A");
//        g.addNode("B");
//        g.addNode("C");
//        g.addNode("D");
//        g.addNode("E");
//
//
//        g.addEdge("A","B");
//        g.addEdge("A","E");
//        g.addEdge("B","D");
//        g.addEdge("B","C");
//        g.addEdge("C","D");
//        g.traverseBreadFirst("A")
// -----------------------------------------------------------
        //拓扑
//        g.addNode("A");
//        g.addNode("B");
//        g.addNode("C");
//        g.addNode("D");
//
//
//        g.addEdge("A","B");
//        g.addEdge("A","C");
//        g.addEdge("B","D");
//        g.addEdge("C","D");
//        g.topologicalSort();
        //-------------------------------------------
//闭环探测
        g.addNode("A");
        g.addNode("B");
        g.addNode("C");


        g.addEdge("A","B");
        g.addEdge("B","C");
        g.addEdge("A","C");
        System.out.println(g.hasCycle());



    }
}
